package com.example.algorithms;

/**
 * Created by Geekkiller on 2017/10/24.
 */
public class QuickSort {

    /**
     * 何为快速排序？
     * 定义：快速排序是一种交换排序。是一种：分治思想
     * 快速排序由C. A. R. Hoare在1962年提出。
     * 它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。
     * 我的理解是： 选择待排序列中找到一个作为基数; 通过比较分割成两部分；左边都设计比基基数大的数而右边则都是比基数小的数；
     * 然后将分割好的；两部分重复上述操作；
     */


    public int division(int[] list, int left, int right) {

        //理论是可以顺便找一个基数
        //以最左边的为（left）基数
        int base = list[left];
        while (left < right) {
            while (left < right && list[right] >= base)
                right--;
            list[left] = list[right];

            while (left < right && list[left] <= base)
                left++;
            list[right] = list[left];
        }

        list[left] = base;
        return left;
    }

    private void quickSort(int[] list, int left, int right) {

        // 左下标一定小于右下标，否则就越界了
        if (left < right) {
            // 对数组进行分割，取出下次分割的基准标号
            int base = division(list, left, right);

            System.out.format("base = %d:\t", list[base]);
            printPart(list, left, right);

            // 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
            quickSort(list, left, base - 1);

            // 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
            quickSort(list, base + 1, right);
        }
    }

    // 打印序列
    public void printPart(int[] list, int begin, int end) {
        for (int i = 0; i < begin; i++) {
            System.out.print("\t");
        }
        for (int i = begin; i <= end; i++) {
            System.out.print(list[i] + "\t");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // 初始化一个序列
        int[] array = {
                1, 3, 4, 5, 2, 6, 9, 7, 8, 0
        };

        // 调用快速排序方法
        QuickSort quick = new QuickSort();
        System.out.print("排序前:\t\t");
        quick.printPart(array, 0, array.length - 1);
        quick.quickSort(array, 0, array.length - 1);
        System.out.print("排序后:\t\t");
        quick.printPart(array, 0, array.length - 1);
    }

}